package primary.code08;

import lombok.extern.slf4j.Slf4j;
import primary.util.ArrayUtils;

/**
 * 问题：岛屿数量
 * <p>
 * 一个矩阵中只有0（水）和1（陆地）两种值，每个陆地只能与上、下、左、右方
 * 如果有一片陆地相联，则这一片陆地被称为一座岛屿。
 * 请问：给定的矩阵中，有多少个岛屿？
 * <p>
 * 分析二
 * <p>
 * 利用递归的思想，修改自身的值为0，并把问题分解为上下左右四个问题。
 */
@Slf4j
public class Code02_NumIslands_2 {

    public static int numIslands(int[][] arr) {
        int num = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j] == 1) {
                    infect(arr, i, j);
                    num++;
                }
            }
        }
        return num;
    }

    private static void infect(int[][] arr, int i, int j) {
        if (i < 0 || i >= arr.length
                || j < 0 || j >= arr[0].length
                || arr[i][j] != 1) {
            return;
        }
        arr[i][j] = 0;
        infect(arr, i - 1, j);
        infect(arr, i + 1, j);
        infect(arr, i, j - 1);
        infect(arr, i, j + 1);
    }

    public static void main(String[] args) {
        int[][] arr = {
                {0, 1, 1, 0, 0},
                {0, 1, 0, 0, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 0, 1},
                {1, 1, 0, 0, 1}
        };
        ArrayUtils.print(arr);
        int num = numIslands(arr);
        log.info("{}", num);
    }
}
